package main

import (
	"fmt"
	"math"
)

/**
狄克斯特拉算法用于在加权图中查找最短路径。
仅当权重为正时狄克斯特拉算法才管用。
如果图中包含负权边，请使用贝尔曼福德算法。

迪克斯特拉(Dijkstra)算法,最短路径算法，和广度优先算法不同的是，每个路径都有权重值，并且是有向无环图DAG

起点->a 需要6分钟
起点->b 需要2分钟
a->终点 需要1分钟
b->a    需要1分钟
b->终点  需要5分钟
可以画图表示

找出用时最短的路径
 */
func main()  {

	//各个点到对应节点的距离
	graph := make(map[string]map[string]int,10)
	graph["start"] = map[string]int{"a":6,"b":2}
	graph["a"] = map[string]int{"fin":1}
	graph["b"] = map[string]int{"a":1,"fin":5}
	graph["fin"] = map[string]int{}

	//节点对应的最小路痴
	costs := make(map[string]int,3)
	costs["a"] = 6
	costs["b"] = 2
	//把不能确定的都用最大整数代替，相当于无穷大∞
	costs["fin"] = math.MaxInt64

	parent := make(map[string]string,3)
	parent["a"] = "start"
	parent["b"] = "start"
	parent["fin"] = ""
	dijkstra(graph,costs,parent)
	fmt.Println(costs)
	fmt.Println(parent)
}

/**
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点的邻居的开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
 */
func dijkstra(graph map[string]map[string]int,costs map[string]int,parent map[string]string) {
	//处理过的节点
	processed:=make([]string,0)
	leastCostNode := findLeastCost(processed, costs)

	for leastCostNode!=""{
		cost:= costs[leastCostNode]
		neighbors := graph[leastCostNode]
		for k,v := range neighbors{
			newCost := cost+v
			if costs[k]>newCost{
				costs[k] = newCost
				parent[k] = leastCostNode
			}
		}
		processed = append(processed, leastCostNode)

		//继续找下一个未处理的最小距离的节点
		leastCostNode = findLeastCost(processed,costs)
	}
}

func findLeastCost(processed []string, costs map[string]int) string {
	leastCost := math.MaxInt64
	leastCostNode := ""

	for k,v := range costs{
		if v<leastCost  && !isContain(processed,k){
			leastCost = v
			leastCostNode = k
		}
	}
	return leastCostNode
}

/**
数据是否包含某元素
*/
func isContain(friends []string, dest string) bool {
	for _,name:=range friends{
		if name==dest{
			return true
		}
	}
	return false
}